/*
 * @lc app=leetcode.cn id=1601 lang=typescript
 *
 * [1601] 最多可达成的换楼请求数目
 */

// @lc code=start
function maximumRequests(n: number, requests: number[][]): number {
  // 检查当前数字二进制位1的数量，也就是请求的数量
  const getRequests = (num: number): number => {
    let ret = 0;
    while (num > 0) {
      ret++;
      num &= num - 1;
    }
    return ret;
  };
  // 检查请求的合法性
  const checkRequest = (mask: number): boolean => {
    // 每栋楼的空闲房间数
    const delta = new Array(n).fill(0);
    for (let i = 0; i < m; i++) {
      // 处理当前请求
      if ((mask & (1 << i)) !== 0) {
        const [from, to] = requests[i];
        // 搬出，空闲房间数+1
        delta[from]++;
        // 搬入，空闲房间数-1
        delta[to]--;
      }
    }
    for (const x of delta) {
      // 如果有空闲房间数不等于0，则不满足题目条件
      if (x !== 0) {
        return false;
      }
    }
    return true;
  };

  const m = requests.length;
  let ans = 0;
  // 枚举所有可能的请求
  // 数字的二进制位为1的话，表示选择了该位置对应的request
  for (let mask = 1; mask < 1 << m; mask++) {
    const cnt = getRequests(mask);
    if (cnt <= ans) continue;
    if (checkRequest(mask)) ans = cnt;
  }
  return ans;
}
// @lc code=end
